package main

import "fmt"

type TreeNode struct {
	Value int
	Left  *TreeNode
	Right *TreeNode
}

type DNode struct {
	Depth int
	Node  *TreeNode
	Next  *DNode
}

func DNodeConstructor(root *TreeNode, depth int) *DNode {
	if root == nil {
		return nil
	}
	var result *DNode = &DNode{
		Depth: depth,
		Node:  root,
	}

	frand := result
	tail := result

	for {
		if frand.Node.Left != nil {
			tail.Next = &DNode{
				Depth: frand.Depth + 1,
				Node:  frand.Node.Left,
			}
			tail = tail.Next
		}
		if frand.Node.Right != nil {
			tail.Next = &DNode{
				Depth: frand.Depth + 1,
				Node:  frand.Node.Right,
			}
			tail = tail.Next
		}
		frand = frand.Next
		if frand == tail {
			return result
		}
	}
}

func PrintBtreeRightSide(root *TreeNode) (s []int) {
	l := DNodeConstructor(root, 0)

	if l == nil {
		return
	}

	for {
		if l.Next == nil {
			s = append(s, l.Node.Value)
			return
		}
		if l.Depth != l.Next.Depth {
			s = append(s, l.Node.Value)
		}
		l = l.Next
	}
}

func main() {
	var root *TreeNode
	var tmp []*TreeNode
	vs := []int{2, 3, 4, 5, 6, 0, 7}
	root = &TreeNode{
		Value: 1,
	}
	tmp = append(tmp, root)
	i := 0
	for {
		if i >= len(vs) {
			break
		}
		if vs[i] != 0 {
			t := &TreeNode{
				Value: vs[i],
			}
			tmp[0].Left = t
			tmp = append(tmp, t)
		}
		if i+1 == len(vs) {
			break
		}
		if vs[i+1] != 0 {
			t := &TreeNode{
				Value: vs[i+1],
			}
			tmp[0].Right = t
			tmp = append(tmp, t)
		}
		i = i + 2
		tmp = tmp[1:]
	}
	fmt.Println(PrintBtreeRightSide(root))
}
